package lc;
import java.util.*;
import org.junit.*;
public class Ex227_2 {
    class Solution {
        public int calculate(String s) {
            char[] cs = s.toCharArray();
            int n = s.length(), i = -1, j = -1;
            char[] cals = new char[n];
            int[] nums = new int[n];
            Map<Character, Integer> map = new HashMap<>(){{
                put('+', 1);
                put('-', 1);
                put('*', 2);
                put('/', 2);
            }}; 
            for (int k = 0; k < n; k++) {
                int t;
                if (cs[k] == ' ') {
                    continue;
                } else if ((t = parseDigit(cs[k])) >= 0) {
                    int c = k;
                    int cur = 0;
                    while (c < n && (t = parseDigit(cs[c])) >= 0) {
                        cur = cur * 10 + t;
                        c++;
                    }
                    nums[++j] = cur;
                    k = c - 1;
                } else if (cs[k] == ')') {
                    while (cals[i] != '(') {
                        char c = cals[i--];
                        int b = nums[j--];
                        int a = nums[j--];
                        nums[++j] = calc(a, c, b);
                    }
                    i--;
                } else {
                    while (i >= 0 && t <= map.get(cals[i])) {
                        char c = cals[i--];
                        int b = nums[j--];
                        int a = nums[j--];
                        nums[++j] = calc(a, c, b);
                    }
                    cals[++i] = cs[k];
                }
            }
            while (i >= 0) {
                char c = cals[i--];
                int b = nums[j--];
                int a = nums[j--];
                nums[++j] = calc(a, c, b);
            }
            return nums[0];
        }

        private int calc(int a, char c, int b) {
            switch(c) {
                case '+': return a + b;
                case '-': return a - b;
                case '*': return a * b;
                case '/': return a / b;
                default: return 0;
            }
        }

        private int parseDigit(char c) {
            if (c < '0' || c > '9') {
                return -1;
            } else {
                return c - '0';
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.calculate("1-1+1"));        
    }
}
